package xt5_最长回文子串;

import java.util.HashMap;
import java.util.Map;

/**
 * 描述:给定一个字符串 s，找到 s 中最长的回文子串。你可以假设 s 的最大长度为 1000。（回文的意思是正着念和倒着念一样，如：上海自来水来自海上）
 *
 * 示例 1：
 *
 * 输入: "babad"
 * 输出: "bab"
 * 注意: "aba" 也是一个有效答案。
 * 示例 2：
 *
 * 输入: "cbbd"
 * 输出: "bb"
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/longest-palindromic-substring
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 *
 * @author lijinhong
 * @date 20.12.24
 */
public class Solution {

    public static void main(String[] args) {
        System.out.println(longestPalindrome("abccd"));
    }

    //时间复杂度O(n)
    public static String longestPalindrome(String s) {
        //记录最长子串的起始位置
        int start = 0, end = -1, subLength = 0;

        Map<String, Integer> map = new HashMap<>();
        //遍历一遍字符串，确定每个字符的索引
        for (int i = 0; i < s.length(); i++) {
            //包含第一个不包含第二个字符时
            if (map.containsKey(String.valueOf(s.charAt(i)))){
                if (!map.containsKey(s.charAt(i)+"2"))
                    map.put(String.valueOf(s.charAt(i))+"2", i);
            }else {
                map.put(String.valueOf(s.charAt(i)), i);
            }
        }
        //在遍历一次字符串，获取每个字符的回文子串的长度
        for (int i = 0; i < s.length(); i++) {
            //包含第一个字符&&包含第二个字符时
            if (map.containsKey(String.valueOf(s.charAt(i))) && map.containsKey(s.charAt(i)+"2")){
                Integer tempStart = map.get(String.valueOf(s.charAt(i)));
                Integer tempEnd = map.get(s.charAt(i)+"2");
                if ( (end - start) < (tempEnd - tempStart) ){
                    end = tempEnd;
                    start = tempStart;
                }
            }
        }

        return s.substring(start, end + 1);
    }
}
